package cn.zzf.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <pre>{@code
 * 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
 * 0 <= a, b, c, d < n
 * a、b、c 和 d 互不相同
 * nums[a] + nums[b] + nums[c] + nums[d] == target
 * 你可以按 任意顺序 返回答案 。
 * 示例 1：
 * 输入：nums = [1,0,-1,0,-2,2], target = 0
 * 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
 * 示例 2：
 * 输入：nums = [2,2,2,2,2], target = 8
 * 输出：[[2,2,2,2]]
 * 提示：
 * 1 <= nums.length <= 200
 * -109 <= nums[i] <= 109
 * -109 <= target <= 109
 * }</pre>
 *
 * @author zzf
 * @date 2025-06-14 12:01
 */
public class T0018_FourSum {

    /**
     * 效率低下，时间复杂度O(n^4)
     *
     * @param nums
     * @param target
     * @return
     * @author zzf
     * @date 2025-06-14 16:55
     */
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int length = nums.length;
        if (length < 4) return ans;

        // 这两个值固定后，就相当于求内侧两个值+外侧两个值-target = 0
        long max = (long) nums[length - 1] + nums[length - 2] + nums[length - 3] + nums[length - 4];
        long min = (long) nums[0] + nums[1] + nums[2] + nums[3];
        if (max < target || min > target) return ans;
        // 双重双指针，外指针一侧用于计算临时target(tmpTarget = oLeft - target, 此时就相当于三数之和了)，一侧作为锚点。
        // 外部双指针
        for (int oLeft = 0; oLeft < length; oLeft++) {
            // 去重
            if (oLeft > 0 && nums[oLeft] == nums[oLeft - 1]) continue;
            for (int oRight = length - 1; oRight > oLeft + 2; oRight--) {
                // 去重
                if (oRight < length - 1 && nums[oRight] == nums[oRight + 1]) continue;
                // 计算临时target
                long outTarget = (long) nums[oLeft] + nums[oRight] - target;

                // 另外三个取最大值都小于0，说明不可能有解
                if (outTarget + nums[oRight - 1] + nums[oRight - 2] < 0) {
                    break;
                }
                // 同理
                // 右侧最大值 + 另外三个取最小值都大于0，说明不可能有解
                if (outTarget + nums[oLeft + 1] + nums[oLeft + 2] > 0) {
                    continue;
                }
                for (int iLeft = oLeft + 1; iLeft < oRight - 1; iLeft++) {
                    // 去重
                    if (iLeft > oLeft + 1 && nums[iLeft] == nums[iLeft - 1]) continue;

                    for (int iRight = oRight - 1; iRight > iLeft; iRight--) {
                        // 去重
                        if (iRight < oRight - 1 && nums[iRight] == nums[iRight + 1]) continue;

                        // 外侧固定情况下，如果加上两个最大值还小于0，说明不可能有解
                        if (outTarget + nums[iRight] + nums[iRight + 1] < 0) {
                            break;
                        }
                        // 同理
                        // 外侧固定情况下，如果加上两个最小值还大于0，说明不可能有解
                        if (outTarget + nums[iLeft] + nums[iLeft + 1] > 0) {
                            continue;
                        }
                        long sum = outTarget + nums[iLeft] + nums[iRight];
                        if (sum == 0) {
                            ans.add(Arrays.asList(nums[oLeft], nums[iLeft], nums[iRight], nums[oRight]));
                            break;
                        }
                    }
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(fourSum(new int[]{1000000000, 1000000000, 1000000000, 1000000000}, -294967296));
        System.out.println(fourSum(new int[]{0, 0, 0, 1000000000, 1000000000, 1000000000, 1000000000}, 1000000000));
        System.out.println(fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0));
        System.out.println(fourSum(new int[]{-1, 0, -5, -2, -2, -4, 0, 1, -2}, -9));
        System.out.println(fourSum(new int[]{-3, -1, 0, 2, 4, 5}, 2));
        System.out.println(fourSum(new int[]{2, 2, 2, 2, 2}, 8));
    }

}
